大话系列 | 决策树（中）—相亲？怎么说
↑关注+星标，听说他有点东西
全文共3078字，阅读全文需16分钟
情景四：穷追不舍没没没
韩梅梅听完母亲描述的《许媒婆之决策树相亲》，一时大感兴趣，自己稍稍补课之后决定来学习学习
和韩梅梅一起补课的请猛击：大话系列|决策树（上）—相亲？怎么说？
韩梅梅：许姨，我稍稍了解了一下决策树，你这个名单是基于决策树哪个算法的？
许媒婆：（眼睛一亮）梅梅你也懂这个啊，那我来给你说道说道
CART分类树
这个名单是基于CART算法来实现的，先来看CART算法
CART：Classification And Regression Tree 分类回归树。
和前两种算法不同，CART算法是通过基尼指数反映样本的不纯度
韩梅梅：什么是基尼系数？
基尼系数常用在经济学中，它是用来衡量一个国家收入差距的常用指标。
当基尼系数大于 0.4 的时候，说明财富差异悬殊。基尼系数在 0.2-0.4 之间说明分配合理，财富差距不大。
另外啊，ID3 和 C4.5 算法可以生成二叉树或多叉树，而 CART 只支持二叉树。
同时 CART 决策树可以作分类树，又可以作回归树。
许媒婆：既然是二叉树，有没有想起一个概率论知识，二项分布？
是了，当一个分支节点的概率为p，另一个就为1-p，这个二项分布的概念，这里也可以拿来用
所以就有了下面这个公式：
也稍微解释一下，当基尼指数越小的时候，说明样本之间的差异性小，越容易区分。
比如：A节点的两个属性概率分别是0.5和0.5，B节点的两个属性概率分别是0.1和0.9，
根据基尼指数：Gini(A) = 0.5， Gini(B) = 0.18，所以选择B节点进行划分
韩梅梅：CART算法在相亲这里怎么用的？
CART算法可用于两类问题，一类就是相亲这种的分类问题，一类就是回归问题。
和上面的例子一样，在每个特征节点通过计算基尼系数，选择基尼系数最小到的特征，然后一直往下划分，最终的决策树就生成了。
其实过程和前面的ID3、C4.5是一样的，只是这里划分特征用的方法不同而已
韩梅梅：懂了懂了，那为什么不在这用CART回归树来解决呢？
许媒婆：回归树？我猜你还不懂回归是什么吧，我给你讲讲
CART回归树
回归树是用来解决连续变量的问题，预测的也是连续值，像预测身高、预测房价这些都属于回归类问题
在 CART 分类树中采用的是基尼系数作为标准，那么在 CART 回归树中，如何评价“不纯度”呢？
韩梅梅：距离？
对，但不全对，我们根据样本的离散程度来评价“不纯度”
样本的离散程度需要先计算所有样本的均值，然后计算每个样本值到均值的差值。
许媒婆：我来举个例子吧
我们假设 x 为样本的个体，均值为 μ。
为了统计样本的离散程度，我们可以取差值的绝对值，或者方差。
如果取差值的绝对值，也就是使用最小绝对偏差（LAD）进行目标函数最优化。
其中：差值的绝对值=样本值减去样本均值的绝对值：
如果取方差，也就是使用最小二乘偏差（LSD）进行目标函数的最优化。
方差为每个样本值减去样本均值的平方和除以样本个数：
其他的过程和分类树是一样的，也就关于不纯度的评价标准不一样
对了，在回归树中，常用最小二乘偏差进行节点划分。
韩梅梅：那这个树是怎么生成的呢？
这个就是决策树的生成问题，我们前面已经说了关于ID3、C4.5和CART算法的特征节点划分，也粗略的说了树的生成过程。
下面我们把整个过程串起来
决策树的生成
首先需要了解几个决策树的概念：
根节点：树的最顶端，最开始的那个节点。
分支节点：树中间的非叶子节点
叶子节点：树最底部的节点，也就是决策结果。
决策树的生成就是要生成一颗由根节点、分支节点和叶子节点组成的树，这棵树可以实现对未知结果的预测
在树的生成过程中，可以通过ID3、C4.5、CART算法自上而下的实现节点的划分
韩梅梅：对了，许姨，你这个名单的准确率是多少呢？
许媒婆：（微微一笑）梅梅你的问题可真多噢，是不是对名单里的哪个男孩子动心思了？
韩梅梅：我保证这是最后一个问题!都还没见面呢，哪有动心的男孩子，许姨说笑了
许媒婆：行，那我就给你透个底
目前我的相亲名册里面已经整理好的数据就几千条
但是你也知道，决策树是一个有监督的分类算法，需要已经打好标签的数据进行模型
人工打标签是很累的，我都整理好几天了，才整理了一小部分
而且你这次要是能相亲成功，又能帮许姨扩充一下训练数据集了
[许媒婆狡黠一笑……]
情景五：明眸善睐道不对
韩梅梅：许姨，我发现这个决策树有点点问题
许媒婆：什么问题，你说说看？
韩梅梅：你看这个决策树的图，左下角这个分支不太对，可以直接删掉这个分支
许媒婆：果然是“人漂亮，眼睛也亮”，这个啊，是需要剪枝的
韩梅梅：（羞涩一笑）剪…剪枝？
许媒婆：来我给你讲讲
为什么要剪枝呢？
剪枝的操作是为了解决决策树的过拟合问题，如果模型不存在过拟合，可以不进行剪枝操作
提到了过拟合问题，举个例子解释一下吧
期末考试前小一老师出了一份模拟试卷，因为是开卷考试，小房同学考了99分，结果期末考试是闭卷，小房同学只考了59分。
从模型拟合的角度讲，小房同学在模拟试卷上表现优秀，但是在期末试卷上表现很差，这叫过拟合。
如果小房同学在模拟试卷上表现很差，但是在期末试卷上表现也很差，这叫欠拟合。
韩梅梅：过拟合和欠拟合懂了，那怎么避免这种现象的发生？
对于决策树的过拟合现象，可以通过剪枝提高模型的预测能力，剪枝包括预剪枝和后剪枝。
剪枝操作如果要细说估计怕是没个几千字说不完，这里就概括一下
预剪枝
顾名思义，预先剪枝。在决策树生成过程中，对每个节点在划分前先进行估计，如果当前节点的划分不能提升模型的预测能力，则停止划分并且将该节点标记为叶子节点
通俗的说，如果当前节点划分了，却没有带来预测能力的提升，那就不用继续下去了
后剪枝
在决策树生成以后，自底向上的对分支节点进行遍历，计算若将分支节点替换为叶子节点能否对预测能力有所提升，若有，则将该子树替换为叶子节点
通俗的讲，在决策树构造好之后，从下向上把每个分支节点变成叶子节点，若有所提升，则进行剪枝
一般来说，预剪枝是在构造决策树的过程中进行剪枝，所有它的时间开销会小很多，但是由于它剪掉的分枝只是当前最优解，所以它的预测能力要弱于后剪枝。
另外，在sklearn 中只提供了决策树的预剪枝的代码接口，需要注意
情景六：媒婆送上纸玫瑰
许媒婆：梅梅啊，名单也给你了，你觉得有什么问题没？
韩梅梅：（略略紧张）没…没没，没有问题，许姨我再考虑考虑。
许媒婆：好，那剩下的就靠你自己了，我这有个纸玫瑰
送给你，加油噢 许媒婆：另外，看你还对决策树挺感兴趣的，这个给你👇
稍稍总结一下决策树
决策树的构造包括三步：特征选择、决策树生成和决策树剪枝
特征选择可以通过信息增益（ID3）、信息增益率（C4.5）、基尼指数（CART）三种方式进行特征的划分选择
决策树生成是通过特征选择，将每个特征属性进行组合组成一棵二叉或多叉树
决策树剪枝对决策树进行剪枝操作，以提高决策树模型的预测能力。
决策树算法的区别与优缺点
ID3算法
基于信息增益进行特征选择，选择信息增益最大属性进行特征划分
可以生成二叉树和多叉树
只可对离散型数据进行分类预测
C4.5算法
基于信息增益率进行特征选择，在信息增益高于平均水平的属性中选择信息增益率最大的属性进行特征划分
可以生成二叉树和多叉树
可以将连续数据离散化之后进行分类预测
可以针对缺失数据进行预测
CART算法
基于基尼指数进行特征选择，选择基尼系数最小的属性进行特征划分
只可以生成二叉树
可预测分类问题，也可以预测回归问题
最后，给你这个
写在后面的话
决策树写完了，但是我们事没完
细心的同学会发现，这篇的标题是中篇，所以还有一个决策树下篇
透露一下，决策树下篇主要是实战
如果思维导图被二压了，大家可以在后台回复决策树获取。我猜八成会被二压，因为这张图原图2.3M
好了，这节就到这了
我是小一，我们 下节见
好巧啊，你也读到这了！
点个在看让小一看到你